package com.lb.algorithm;

/**
 * @version 1.0
 * @Author: Edward
 * @Date: 2021/10/16 15:16
 * @Description:
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {7, 3, 2, 6, 8, 1, 9, 5, 4, 10};
        int[] arr = {1,2,7,6,5,4,3};

        sort(arr, 0, arr.length - 1);

        print(arr);
    }

    public static void sort(int[] arr, int leftBound, int rightBound) {
        if (leftBound >= rightBound) {
            return;
        }

        int mid = partition(arr, leftBound, rightBound);

        sort(arr, leftBound, mid - 1);
        sort(arr, mid + 1, rightBound);
    }

    static int partition(int[] arr, int leftBound, int rightBound) {
        // 定义轴
        int pivot = arr[rightBound];
        // 左侧指针
        int left = leftBound;
        // 右侧指针
        int right = rightBound - 1;

        while (left <= right) {
            while (left <= right && arr[left] <= pivot) {
                left ++;
            }

            while (left <= right && arr[right] > pivot) {
                right --;
            }

            if (left < right) {
                swap(arr, left, right);
            }
        }

        swap(arr, left, rightBound);

        return left;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
